//比较含退格的字符串
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string _s;
        string _t;
        for (auto& c : s) {
            if (_s.size() && c == '#')
                _s.pop_back();
            else if (c != '#')
                _s.push_back(c);
        }
        for (auto& c : t) {
            if (_t.size() && c == '#')
                _t.pop_back();
            else if (c != '#')
                _t.push_back(c);
        }
        return _s == _t;
    }
};

//基本计算器 II
class Solution {
public:
    int calculate(string s) {
        vector<int> stack;
        char c = '+';
        int slow = 0, quick = 0;
        while (quick < s.size()) {
            if (s[quick] != ' ') {
                swap(s[slow], s[quick]);
                slow++;
            }
            quick++;
        }
        s.resize(slow);
        // cout<<s;
        int x, y;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] >= '0' && s[i] <= '9') {
                int temp = 0;
                while (s[i] >= '0' && s[i] <= '9') {
                    temp *= 10;
                    temp += (s[i] - '0');
                    i++;
                }
                // cout << temp << ' ';
                switch (c) {
                case '+':
                    stack.push_back(temp);
                    break;
                case '-':
                    stack.push_back(-temp);
                    break;
                case '*':
                    x = temp;
                    //stack.pop_back();
                    y = stack.back();
                    stack.pop_back();
                    stack.push_back(y * x);
                    break;
                case '/':
                    x = temp;
                    //stack.pop_back();
                    y = stack.back();
                    stack.pop_back();
                    stack.push_back(y / x);
                    break;
                }
            }
            if (i < s.size())
                c = s[i];
           // for (auto& num : stack)
              //  cout << num << '-' << c << ' ';
           // cout << endl;
        }
        int ret = 0;
        for (auto& num : stack)
            ret += num;
        // cout << num << ' ';
        return ret;
    }
};